﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SearchBackEnd
{
    class SearchIndex
    {
        /// <summary>
        /// the inverted index - a map from term string to list of docIDs.
        /// </summary>
        private Dictionary<String, List<long>> invertedIndex = new Dictionary<string, List<long>>();
        /// <summary>
        /// a map from docIDs to doc name.
        /// </summary>
        private Dictionary<long, String> fileIdToName = new Dictionary<long, string>();
        /// <summary>
        /// a map from doc name to docIDs.
        /// </summary>
        private Dictionary<String, long> fileNameToId = new Dictionary<string, long>();

        private long m_PageNumber = 0;
        /// <summary>
        /// Adds a page to the index.
        /// </summary>
        /// <param name="page">The page to index.</param>
        public void AddToIndex(Page page)
        {
            String[] keyWords = page.Content.Split(' ');
            HashSet<String> uniqueKeyWords = new HashSet<string>(keyWords);
            if (uniqueKeyWords.Count == 0) return;
            m_PageNumber++;
            //assign a unique id to the page.
            fileIdToName.Add(m_PageNumber, page.Name);
            fileNameToId.Add(page.Name, m_PageNumber);
            //add page terms to posting lists.
            foreach (string key in uniqueKeyWords)
            {
                if (!invertedIndex.ContainsKey(key))
                    invertedIndex.Add(key, new List<long>());
                invertedIndex[key].Add(m_PageNumber);
            }
            //Console.WriteLine("Done!");
        }

        public Boolean RemovePageFromIndex(Page page)
        {
            if (!fileNameToId.ContainsKey(page.Name)) return false;

            List<String> termsToRemove = new List<string>();
            //get page id
            long pageId = fileNameToId[page.Name];
            //remove id from all of the posting lists.
            foreach (String term in invertedIndex.Keys)
            {
                List<long> postingList = invertedIndex[term];
                postingList.Remove(pageId);
                if (postingList.Count == 0) termsToRemove.Add(term);
            }
            //removing empty posting lists
            foreach (String t in termsToRemove)
            {
                invertedIndex.Remove(t);
            }

            fileNameToId.Remove(page.Name);
            fileIdToName.Remove(pageId);
            return true;
        }

        /// <summary>
        /// Search the given words in the index - searching for a document which contains all of the words.
        /// </summary>
        /// <param name="words">array of keywords.</param>
        /// <returns>array of all the file names that matched the query.</returns>
        public string[] SearchPage(String[] words)
        {
            Console.Write("Searching for keywords: ");
            foreach (String kw in words)
                Console.Write(kw + " ");
            Console.WriteLine();
            List<String> result = new List<string>();

            List<List<long>.Enumerator> postingLists = new List<List<long>.Enumerator>();
            if (words.Length == 0)
            {
                return new string[0];
            }
            //get the posting lists of the keywords
            foreach (string keyWord in words)
            {
                List<long> keyWordPostingList = null;

                if (!invertedIndex.TryGetValue(keyWord, out keyWordPostingList))
                {
                    //no such keyword in the index - return - no results.
                    Console.WriteLine("No results found.", result.ToString());
                    return new String[0];
                }

                List<long>.Enumerator iter = keyWordPostingList.GetEnumerator();
                iter.MoveNext();
                postingLists.Add(iter);
            }

            //going over the posing lists to get results.
            List<long>.Enumerator[] postingListsArr = postingLists.ToArray();
            long maxId = -1;
            while (true)
            {
                //true iff all the posting lists point to the same page
                bool allSame = true;

                //try to align posting lists on the same id.
                for (int i = 0; i < postingListsArr.Length; i++)
                {

                    if (postingListsArr[i].Current < maxId)
                        if (!SkipTo(postingListsArr[i], maxId))
                        {
                            Console.WriteLine("found {0} results", result.Count);
                            return result.ToArray();
                        }
                    if (postingListsArr[i].Current > maxId)
                    {
                        allSame = false;
                        maxId = postingListsArr[i].Current;
                    }
                }
                if (!allSame) continue;
                //add result to result set.
                result.Add(fileIdToName[maxId]);
                //move all posting lists to the next page.
                for (int i = 0; i < postingListsArr.Length; i++)
                    if (!postingListsArr[i].MoveNext())
                    {
                        Console.WriteLine("found {0} results", result.Count);
                        return result.ToArray();
                    }
            }
        }

        /// <summary>
        /// Given an enumerator (sorted) skips to the minimal id so it is equal or bigger than the input id.
        /// </summary>
        /// <param name="iter">the enumerator</param>
        /// <param name="id">the input id.</param>
        /// <returns>true iff such an id exists.</returns>
        private bool SkipTo(List<long>.Enumerator iter, long id)
        {
            bool hasNext = true;
            while (iter.Current < id && hasNext)
                hasNext = iter.MoveNext();

            return hasNext;
        }       
    }
}


